package org.pupil.tree;

import java.util.Stack;

/**
 * @Description: 二叉树
 * @Author: pupil
 * @Date: 2024/08/06 下午 12:30
 */
public class TreeNode {
    private int value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

    // 先序遍历递归版 中左右
    public static void preOrder1(TreeNode head) {
        if (head == null) {
            return;
        }
        System.out.print(head.value + " ");
        preOrder1(head.left);
        preOrder1(head.right);
    }

    // 中序遍历递归版 左中右
    public static void inOrder1(TreeNode head) {
        if (head == null) {
            return;
        }
        inOrder1(head.left);
        System.out.print(head.value + " ");
        inOrder1(head.right);
    }

    // 后序遍历递归版 左右中
    public static void posOrder1(TreeNode head) {
        if (head == null) {
            return;
        }
        posOrder1(head.left);
        posOrder1(head.right);
        System.out.print(head.value + " ");
    }

    // 先序遍历，非递归版本，栈实现
    public static void preOrder2(TreeNode head) {
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.print(head.value + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
            System.out.println();
        }
    }

    // 中序遍历，非递归版本，栈实现
    public static void inOrder2(TreeNode head) {
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
            System.out.println();
        }
    }

    // 后序遍历，非递归版本，双栈实现
    // 先序：中左右
    // 先序`：中右左    倒序后就是后序遍历
    // 后序：左右中
    public static void posOrder2(TreeNode head) {
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> collect = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                collect.push(head);
                if (head.left != null) {
                    stack.push(head.left);
                }
                if (head.right != null) {
                    stack.push(head.right);
                }
            }
            while (!collect.isEmpty()) {
                System.out.print(collect.pop().value + " ");
            }
            System.out.println();
        }
    }

    // 后序遍历，非递归版本，单栈实现
    public static void posOrderOneStack(TreeNode h) {
        if (h != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(h);
            // 如果始终没有打印过节点，h就一直是头节点
            // 一旦打印过节点，h就变成打印节点
            // 之后h的含义：上一次打印的节点
            while (!stack.isEmpty()) {
                TreeNode cur = stack.peek();
                if (cur.left != null
                        && h != cur.left
                        && h != cur.right) {
                    // 有左树且左数没有被处理
                    stack.push(cur.left);
                } else if (cur.right != null
                        && h != cur.right) {
                    // 有右树且右数没有被处理
                    stack.push(cur.right);
                }else {
                    // 左数 右数 没有 或者 处理过了
                    System.out.print(cur.value + " ");
                    h = stack.pop();
                }
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(5);
        head.right.left = new TreeNode(6);
        head.right.right = new TreeNode(7);

        System.out.println("先序遍历递归版");
        preOrder1(head);
        System.out.println();

        System.out.println("中序遍历递归版");
        inOrder1(head);
        System.out.println();

        System.out.println("后序遍历递归版");
        posOrder1(head);
        System.out.println();
        System.out.println();

        System.out.println("先序遍历非递归版");
        preOrder2(head);
        System.out.println();

        System.out.println("中序遍历非递归版");
        inOrder2(head);
        System.out.println();

        System.out.println("后序遍历非递归版");
        posOrder2(head);
        System.out.println();

        System.out.println("后序遍历非递归版,单栈实现");
        posOrderOneStack(head);
        System.out.println();

    }

}

